home *** CD-ROM | disk | FTP | other *** search
/ Apple Developer Connection Student Program / ADC Tools Sampler CD Disk 3 1999.iso / Metrowerks CodeWarrior / Java Support / Java_Source / Java2 / src / java / util / TreeSet.java < prev    next >
Encoding:
Java Source  |  1999-05-28  |  17.4 KB  |  449 lines  |  [TEXT/CWIE]
  1. /*
  2.  * @(#)TreeSet.java    1.13 98/09/30
  3.  *
  4.  * Copyright 1998 by Sun Microsystems, Inc.,
  5.  * 901 San Antonio Road, Palo Alto, California, 94303, U.S.A.
  6.  * All rights reserved.
  7.  *
  8.  * This software is the confidential and proprietary information
  9.  * of Sun Microsystems, Inc. ("Confidential Information").  You
  10.  * shall not disclose such Confidential Information and shall use
  11.  * it only in accordance with the terms of the license agreement
  12.  * you entered into with Sun.
  13.  */
  14.  
  15. package java.util;
  16.  
  17. /**
  18.  * This class implements the <tt>Set</tt> interface, backed by a
  19.  * <tt>TreeMap</tt> instance.  This class guarantees that the sorted set will
  20.  * be in ascending element order, sorted according to the <i>natural order</i>
  21.  * of the elements (see <tt>Comparable</tt>), or by the comparator provided at
  22.  * set creation time, depending on which constructor is used.<p>
  23.  *
  24.  * This implementation provides guaranteed log(n) time cost for the basic
  25.  * operations (<tt>add</tt>, <tt>remove</tt> and <tt>contains</tt>).<p>
  26.  *
  27.  * Note that the ordering maintained by a set (whether or not an explicit
  28.  * comparator is provided) must be <i>consistent with equals</i> if it is to
  29.  * correctly implement the <tt>Set</tt> interface.  (See <tt>Comparable</tt>
  30.  * or <tt>Comparator</tt> for a precise definition of <i>consistent with
  31.  * equals</i>.)  This is so because the <tt>Set</tt> interface is defined in
  32.  * terms of the <tt>equals</tt> operation, but a <tt>TreeSet</tt> instance
  33.  * performs all key comparisons using its <tt>compareTo</tt> (or
  34.  * <tt>compare</tt>) method, so two keys that are deemed equal by this method
  35.  * are, from the standpoint of the set, equal.  The behavior of a set
  36.  * <i>is</i> well-defined even if its ordering is inconsistent with equals; it
  37.  * just fails to obey the general contract of the <tt>Set</tt> interface.<p>
  38.  *
  39.  * <b>Note that this implementation is not synchronized.</b> If multiple
  40.  * threads access a set concurrently, and at least one of the threads modifies
  41.  * the set, it <i>must</i> be synchronized externally.  This is typically
  42.  * accomplished by synchronizing on some object that naturally encapsulates
  43.  * the set.  If no such object exists, the set should be "wrapped" using the
  44.  * <tt>Collections.synchronizedSet</tt> method.  This is best done at creation
  45.  * time, to prevent accidental unsynchronized access to the set: <pre>
  46.  *     SortedSet s = Collections.synchronizedSortedSet(new TreeSet(...));
  47.  * </pre><p>
  48.  *
  49.  * The Iterators returned by this class's <tt>iterator</tt> method are
  50.  * <i>fail-fast</i>: if the set is modified at any time after the iterator is
  51.  * created, in any way except through the iterator's own <tt>remove</tt>
  52.  * method, the iterator will throw a <tt>ConcurrentModificationException</tt>.
  53.  * Thus, in the face of concurrent modification, the iterator fails quickly
  54.  * and cleanly, rather than risking arbitrary, non-deterministic behavior at
  55.  * an undetermined time in the future.
  56.  *
  57.  * @author  Josh Bloch
  58.  * @version 1.13, 09/30/98
  59.  * @see        Collection
  60.  * @see        Set
  61.  * @see        HashSet
  62.  * @see     Comparable
  63.  * @see     Comparator
  64.  * @see        Collections#synchronizedSortedSet(SortedSet)
  65.  * @see        TreeMap
  66.  * @since JDK1.2
  67.  */
  68.  
  69. public class TreeSet extends AbstractSet
  70.              implements SortedSet, Cloneable, java.io.Serializable
  71. {
  72.     private transient SortedMap m;     // The backing Map
  73.     private transient Set          keySet;  // The keySet view of the backing Map
  74.  
  75.     // Dummy value to associate with an Object in the backing Map
  76.     private static final Object PRESENT = new Object();
  77.  
  78.     /**
  79.      * Constructs a set backed by the given sorted map.
  80.      */
  81.     private TreeSet(SortedMap m) {
  82.         this.m = m;
  83.         keySet = m.keySet();
  84.     }
  85.  
  86.     /**
  87.      * Constructs a new, empty set, sorted according to the elements' natural
  88.      * order.  All elements inserted into the set must implement the
  89.      * <tt>Comparable</tt> interface.  Furthermore, all such elements must be
  90.      * <i>mutually comparable</i>: <tt>e1.compareTo(e2)</tt> must not throw a
  91.      * <tt>ClassCastException</tt> for any elements <tt>e1</tt> and
  92.      * <tt>e2</tt> in the set.  If the user attempts to add an element to the
  93.      * set that violates this constraint (for example, the user attempts to
  94.      * add a string element to a set whose elements are integers), the
  95.      * <tt>add(Object)</tt> call will throw a <tt>ClassCastException</tt>.
  96.      * 
  97.      * @see Comparable
  98.      */
  99.     public TreeSet() {
  100.     this(new TreeMap());
  101.     }
  102.  
  103.     /**
  104.      * Constructs a new, empty set, sorted according to the given comparator.
  105.      * All elements inserted into the set must be <i>mutually comparable</i>
  106.      * by the given comparator: <tt>comparator.compare(e1, e2)</tt> must not
  107.      * throw a <tt>ClassCastException</tt> for any elements <tt>e1</tt> and
  108.      * <tt>e2</tt> in the set.  If the user attempts to add an element to the
  109.      * set that violates this constraint, the <tt>add(Object)</tt> call will
  110.      * throw a <tt>ClassCastException</tt>.
  111.      */
  112.     public TreeSet(Comparator c) {
  113.     this(new TreeMap(c));
  114.     }
  115.  
  116.     /**
  117.      * Constructs a new set containing the elements in the specified
  118.      * collection, sorted according to the elements' <i>natural order</i>.
  119.      * All keys inserted into the set must implement the <tt>Comparable</tt>
  120.      * interface.  Furthermore, all such keys must be <i>mutually
  121.      * comparable</i>: <tt>k1.compareTo(k2)</tt> must not throw a
  122.      * <tt>ClassCastException</tt> for any elements <tt>k1</tt> and
  123.      * <tt>k2</tt> in the set.
  124.      *
  125.      * @param c The elements that will comprise the new set.
  126.      *
  127.      * @throws ClassCastException if the keys in the given collection are not
  128.      * comparable, or are not mutually comparable.
  129.      */
  130.     public TreeSet(Collection c) {
  131.         this();
  132.         addAll(c);        
  133.     }
  134.  
  135.     /**
  136.      * Constructs a new set containing the same elements as the given sorted
  137.      * set, sorted according to the same ordering.
  138.      *
  139.      * @param s sorted set whose elements will comprise the new set.
  140.      */
  141.     public TreeSet(SortedSet s) {
  142.         this(s.comparator());
  143.     addAll(s);
  144.     }
  145.  
  146.     /**
  147.      * Returns an iterator over the elements in this set.  The elements
  148.      * are returned in ascending order.
  149.      *
  150.      * @return an iterator over the elements in this set.
  151.      */
  152.     public Iterator iterator() {
  153.     return keySet.iterator();
  154.     }
  155.  
  156.     /**
  157.      * Returns the number of elements in this set (its cardinality).
  158.      *
  159.      * @return the number of elements in this set (its cardinality).
  160.      */
  161.     public int size() {
  162.     return m.size();
  163.     }
  164.  
  165.     /**
  166.      * Returns <tt>true</tt> if this set contains no elements.
  167.      *
  168.      * @return <tt>true</tt> if this set contains no elements.
  169.      */
  170.     public boolean isEmpty() {
  171.     return m.isEmpty();
  172.     }
  173.  
  174.     /**
  175.      * Returns <tt>true</tt> if this set contains the specified element.
  176.      *
  177.      * @param o the object to be checked for containment in this set.
  178.      * @return <tt>true</tt> if this set contains the specified element.
  179.      * 
  180.      * @throws ClassCastException if the specified object cannot be compared
  181.      *           with the elements currently in the set.
  182.      */
  183.     public boolean contains(Object o) {
  184.     return m.containsKey(o);
  185.     }
  186.  
  187.     /**
  188.      * Adds the specified element to this set if it is not already present.
  189.      *
  190.      * @param o element to be added to this set.
  191.      * @return <tt>true</tt> if the set did not already contain the specified
  192.      *         element.
  193.      * 
  194.      * @throws ClassCastException if the specified object cannot be compared
  195.      *           with the elements currently in the set.
  196.      */
  197.     public boolean add(Object o) {
  198.     return m.put(o, PRESENT)==null;
  199.     }
  200.  
  201.     /**
  202.      * Removes the given element from this set if it is present.
  203.      *
  204.      * @param o object to be removed from this set, if present.
  205.      * @return <tt>true</tt> if the set contained the specified element.
  206.      * 
  207.      * @throws ClassCastException if the specified object cannot be compared
  208.      *           with the elements currently in the set.
  209.      */
  210.     public boolean remove(Object o) {
  211.     return m.remove(o)==PRESENT;
  212.     }
  213.  
  214.     /**
  215.      * Removes all of the elements from this set.
  216.      */
  217.     public void clear() {
  218.     m.clear();
  219.     }
  220.  
  221.     /**
  222.      * Adds all of the elements in the specified collection to this set.
  223.      *
  224.      * @param c elements to be added
  225.      * @return <tt>true</tt> if this set changed as a result of the call.
  226.      *
  227.      * @throws ClassCastException if the elements provided cannot be compared
  228.      *          with the elements currently in the set.
  229.      */
  230.     public boolean addAll(Collection c) {
  231.         // Use linear-time version if applicable
  232.         if (m.size()==0 && c.size() > 0 && c instanceof SortedSet && 
  233.             m instanceof TreeMap) {
  234.             SortedSet set = (SortedSet)c;
  235.             TreeMap map = (TreeMap)m;
  236.             Comparator cc = set.comparator();
  237.             Comparator mc = map.comparator();
  238.             if (cc==mc || (cc != null && cc.equals(mc))) {
  239.                 map.addAllForTreeSet(set, PRESENT);
  240.                 return true;
  241.             }
  242.         }
  243.         return super.addAll(c);
  244.     }
  245.  
  246.     /**
  247.      * Returns a view of the portion of this set whose elements range from
  248.      * <tt>fromElement</tt>, inclusive, to <tt>toElement</tt>, exclusive.  (If
  249.      * <tt>fromElement</tt> and <tt>toElement</tt> are equal, the returned
  250.      * sorted set is empty.)  The returned sorted set is backed by this set,
  251.      * so changes in the returned sorted set are reflected in this set, and
  252.      * vice-versa.  The returned sorted set supports all optional Set
  253.      * operations.<p>
  254.      *
  255.      * The sorted set returned by this method will throw an
  256.      * <tt>IllegalArgumentException</tt> if the user attempts to insert an
  257.      * element outside the specified range.<p>
  258.      *
  259.      * Note: this method always returns a <i>half-open range</i> (which
  260.      * includes its low endpoint but not its high endpoint).  If you need a
  261.      * <i>closed range</i> (which includes both endpoints), and the element
  262.      * type allows for calculation of the successor a given value, merely
  263.      * request the subrange from <tt>lowEndpoint</tt> to
  264.      * <tt>successor(highEndpoint)</tt>.  For example, suppose that <tt>s</tt>
  265.      * is a sorted set of strings.  The following idiom obtains a view
  266.      * containing all of the strings in <tt>s</tt> from <tt>low</tt> to
  267.      * <tt>high</tt>, inclusive: <pre>
  268.      *     SortedSet sub = s.subSet(low, high+"\0");
  269.      * </pre>
  270.      * 
  271.      * A similar technique can be used to generate an <i>open range</i> (which
  272.      * contains neither endpoint).  The following idiom obtains a view
  273.      * containing all of the strings in <tt>s</tt> from <tt>low</tt> to
  274.      * <tt>high</tt>, exclusive: <pre>
  275.      *     SortedSet sub = s.subSet(low+"\0", high);
  276.      * </pre>
  277.      *
  278.      * @param fromElement low endpoint (inclusive) of the subSet.
  279.      * @param toElement high endpoint (exclusive) of the subSet.
  280.      * @return a view of the portion of this set whose elements range from
  281.      *            <tt>fromElement</tt>, inclusive, to <tt>toElement</tt>,
  282.      *            exclusive.
  283.      * @throws NullPointerException if <tt>fromElement</tt> or
  284.      *          <tt>toElement</tt> is <tt>null</tt> and this set uses
  285.      *          natural ordering, or its comparator does not tolerate
  286.      *          <tt>null</tt> elements.
  287.      * @throws IllegalArgumentException if <tt>fromElement</tt> is greater
  288.      * than <tt>toElement</tt>.
  289.      */
  290.     public SortedSet subSet(Object fromElement, Object toElement) {
  291.     return new TreeSet(m.subMap(fromElement, toElement));
  292.     }
  293.  
  294.     /**
  295.      * Returns a view of the portion of this set whose elements are strictly
  296.      * less than <tt>toElement</tt>.  The returned sorted set is backed by
  297.      * this set, so changes in the returned sorted set are reflected in this
  298.      * set, and vice-versa.  The returned sorted set supports all optional set
  299.      * operations.<p>
  300.      *
  301.      * The sorted set returned by this method will throw an
  302.      * <tt>IllegalArgumentException</tt> if the user attempts to insert an
  303.      * element greater than or equal to <tt>toElement</tt>.<p>
  304.      *
  305.      * Note: this method always returns a view that does not contain its
  306.      * (high) endpoint.  If you need a view that does contain this endpoint,
  307.      * and the element type allows for calculation of the successor a given
  308.      * value, merely request a headSet bounded by
  309.      * <tt>successor(highEndpoint)</tt>.  For example, suppose that <tt>s</tt>
  310.      * is a sorted set of strings.  The following idiom obtains a view
  311.      * containing all of the strings in <tt>s</tt> that are less than or equal
  312.      * to <tt>high</tt>: <pre> SortedSet head = s.headSet(high+"\0");</pre>
  313.      *
  314.      * @param toElement high endpoint (exclusive) of the headSet.
  315.      * @return a view of the portion of this set whose elements are strictly
  316.      *            less than toElement.
  317.      * @throws    NullPointerException if toElement is <tt>null</tt> and this
  318.      *          set uses natural ordering, or its comparator does
  319.      *            not tolerate <tt>null</tt> elements.
  320.      */
  321.     public SortedSet headSet(Object toElement) {
  322.     return new TreeSet(m.headMap(toElement));
  323.     }
  324.  
  325.     /**
  326.      * Returns a view of the portion of this set whose elements are
  327.      * greater than or equal to <tt>fromElement</tt>.  The returned sorted set
  328.      * is backed by this set, so changes in the returned sorted set are
  329.      * reflected in this set, and vice-versa.  The returned sorted set
  330.      * supports all optional set operations.<p>
  331.      *
  332.      * The sorted set returned by this method will throw an
  333.      * <tt>IllegalArgumentException</tt> if the user attempts to insert an
  334.      * element less than <tt>fromElement</tt>.
  335.      *
  336.      * Note: this method always returns a view that contains its (low)
  337.      * endpoint.  If you need a view that does not contain this endpoint, and
  338.      * the element type allows for calculation of the successor a given value,
  339.      * merely request a tailSet bounded by <tt>successor(lowEndpoint)</tt>.
  340.      * For example, suppose that <tt>s</tt> is a sorted set of strings.  The
  341.      * following idiom obtains a view containing all of the strings in
  342.      * <tt>s</tt> that are strictly greater than <tt>low</tt>: <pre>
  343.      *     SortedSet tail = s.tailSet(low+"\0");
  344.      * </pre>
  345.      *
  346.      * @param fromElement low endpoint (inclusive) of the tailSet.
  347.      * @return a view of the portion of this set whose elements are
  348.      *            greater than or equal to <tt>fromElement</tt>.
  349.      * 
  350.      * @throws NullPointerException if <tt>fromElement</tt> is <tt>null</tt>
  351.      *           and this set uses natural ordering, or its comparator
  352.      *           does not tolerate <tt>null</tt> elements.
  353.      */
  354.     public SortedSet tailSet(Object fromElement) {
  355.     return new TreeSet(m.tailMap(fromElement));
  356.     }
  357.  
  358.     /**
  359.      * Returns the comparator used to order this sorted set, or <tt>null</tt>
  360.      * if this tree map uses its keys natural ordering.
  361.      *
  362.      * @return the comparator used to order this sorted set, or <tt>null</tt>
  363.      * if this tree map uses its keys natural ordering.
  364.      */
  365.     public Comparator comparator() {
  366.         return m.comparator();
  367.     }
  368.  
  369.     /**
  370.      * Returns the first (lowest) element currently in this sorted set.
  371.      *
  372.      * @return the first (lowest) element currently in this sorted set.
  373.      * @throws    NoSuchElementException sorted set is empty.
  374.      */
  375.     public Object first() {
  376.         return m.firstKey();
  377.     }
  378.  
  379.     /**
  380.      * Returns the last (highest) element currently in this sorted set.
  381.      *
  382.      * @return the last (highest) element currently in this sorted set.
  383.      * @throws    NoSuchElementException sorted set is empty.
  384.      */
  385.     public Object last() {
  386.         return m.lastKey();
  387.     }
  388.  
  389.     /**
  390.      * Returns a shallow copy of this <tt>TreeSet</tt> instance. (The elements
  391.      * themselves are not cloned.)
  392.      *
  393.      * @return a shallow copy of this set.
  394.      */
  395.     public Object clone() {
  396.         return new TreeSet(this);
  397.     }
  398.  
  399.     /**
  400.      * Save the state of the <tt>TreeSet</tt> instance to a stream (that is,
  401.      * serialize it).
  402.      *
  403.      * @serialData Emits the comparator used to order this set, or
  404.      *           <tt>null</tt> if it obeys its elements' natural ordering
  405.      *           (Object), followed by the size of the set (the number of
  406.      *           elements it contains) (int), followed by all of its
  407.      *           elements (each an Object) in order (as determined by the
  408.      *           set's Comparator, or by the elements' natural ordering if
  409.      *             the set has no Comparator).
  410.      */
  411.     private synchronized void writeObject(java.io.ObjectOutputStream s)
  412.         throws java.io.IOException {
  413.     // Write out any hidden stuff
  414.     s.defaultWriteObject();
  415.  
  416.         // Write out Comparator
  417.         s.writeObject(m.comparator());
  418.  
  419.         // Write out size
  420.         s.writeInt(m.size());
  421.  
  422.     // Write out all elements in the proper order.
  423.     for (Iterator i=m.keySet().iterator(); i.hasNext(); )
  424.             s.writeObject(i.next());
  425.     }
  426.  
  427.     /**
  428.      * Reconstitute the <tt>TreeSet</tt> instance from a stream (that is,
  429.      * deserialize it).
  430.      */
  431.     private synchronized void readObject(java.io.ObjectInputStream s)
  432.         throws java.io.IOException, ClassNotFoundException {
  433.     // Read in any hidden stuff
  434.     s.defaultReadObject();
  435.  
  436.         // Read in Comparator
  437.         Comparator c = (Comparator)s.readObject();
  438.  
  439.         // Create backing TreeMap and keySet view
  440.         m = (c==null ? new TreeMap() : new TreeMap(c));
  441.         keySet = m.keySet();
  442.  
  443.         // Read in size
  444.         int size = s.readInt();
  445.  
  446.         ((TreeMap)m).readTreeSet(size, s, PRESENT);
  447.     }
  448. }
  449.